
/*
Description:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1


*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
	/*
	My solutions use binary search guided by the following thoughts:
	Remember the array is sorted, except it might drop at one point.
    If nums[0] <= nums[i], then nums[0..i] is sorted (in case of "==" it's just one element, 
	and in case of "<" there must be a drop elsewhere). So we should keep searching in nums[0..i] 
	if the target lies in this sorted range, i.e., if nums[0] <= target <= nums[i].
    If nums[i] < nums[0], then nums[0..i] contains a drop, and thus nums[i+1..end] is sorted 
	and lies strictly between nums[i] and nums[0]. So we should keep searching in nums[0..i] 
	if the target doesn't lie strictly between them, i.e., if target <= nums[i] < nums[0] or nums[i] < nums[0] <= target

	Those three cases look cyclic:

		nums[0] <= target <= nums[i]
               target <= nums[i] < nums[0]
                         nums[i] < nums[0] <= target

	So I have the three checks (nums[0] <= target), (target <= nums[i]) and (nums[i] < nums[0]), 
	and I want to know whether exactly two of them are true. They can't all be true or all be false (check it), 
	so I just need to distinguish between "two true" and "one true". Parity is enough for that, 
	so instead of adding them I xor them, which is a bit shorter and particularly helpful in Java and Ruby, 
	because those don't let me add booleans but do let me xor them.

	(Actually while developing this I thought of permutations of nums[0], target and nums[i] 
	and the permutation parity and saw those three checks as representing inversions, 
	but I had trouble putting that into words and now find the above explanation much better. 
	But it helped me get there, so I wanted to mention it here.)
	*/
	int search(vector<int>& nums, int target) {
		int lo = 0, hi = int(nums.size()) - 1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
				lo = mid + 1;
			else
				hi = mid;
		}
		return lo == hi && nums[lo] == target ? lo : -1;
	}

	/*
	What a mind-blowing solution!
	Let's say nums looks like this: [12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
	Because it's not fully sorted, we can't do normal binary search. But here comes the trick:
		If target is let's say 14, then we adjust nums to this, where "inf" means infinity:
		[12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

		If target is let's say 7, then we adjust nums to this:
		[-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

	And then we can simply do ordinary binary search.
	Of course we don't actually adjust the whole array but instead adjust only on the fly only the elements we look at. And the adjustment is done by comparing both the target and the actual element against nums[0].

	Code
	If nums[mid] and target are "on the same side" of nums[0], we just take nums[mid]. Otherwise we use -infinity or +infinity as needed.
	*/
	int search2(vector<int>& nums, int target) {
		int lo = 0, hi = nums.size();
		while (lo < hi) {
			int mid = (lo + hi) / 2;

			double num = (nums[mid] < nums[0]) == (target < nums[0])
				? nums[mid]
				: target < nums[0] ? -INFINITY : INFINITY;

			if (num < target)
				lo = mid + 1;
			else if (num > target)
				hi = mid;
			else
				return mid;
		}
		return -1;
	}
	/*
	This is insanely elegant but so difficult to intuitively understand. 
	I felt like a dummy trying to figure this out but I did and I wrote a solution to this with a more verbose 
	and intuitive explanation for dummies like me. 
	My code is also more readable and easy to understand but probably a bit less efficient.
	*/
	int search1(vector<int>& nums, int target)
	{
		int l = 0, r = nums.size() - 1;
		while (l <= r)
		{
			int mid = (r - l) / 2 + l;
			int comparator = nums[mid];
			// Checking if both target and nums[mid] are on same side.
			if ((target < nums[0]) && (nums[mid] < nums[0]) || (target >= nums[0]) && (nums[mid] >= nums[0]))
				comparator = nums[mid];
			else
			{
				// Trying to figure out where nums[mid] is and making comparator as -INF or INF
				if (target <nums[0])
					comparator = -INFINITY;
				else
					comparator = INFINITY;

			}
			if (target == comparator) return mid;
			if (target > comparator)
				l = mid + 1;
			else
				r = mid - 1;

		}
		return -1;
	}

	//You may assume no duplicate exists in the array.
	//Your algorithm's runtime complexity must be in the order of O(log n).
	int search0(vector<int>& nums, int target) {
		if (nums.size() == 0)
			return -1;

		int pos = -1;
		int left = 0;
		int right = nums.size() - 1;
		int mid = 0;
		while (left < right)
		{
			mid = (left + right) / 2;
			if (nums[mid] == target)
			{
				pos = mid;
				break;
			}
			else if (nums[mid] > target)
			{
				if (nums[mid] < nums[left])
				{
					if (nums[left] > target)
					{
						right = mid; 
					}
					else
					{
						left = mid + 1;
					}
				}
				else
				{										
					if (nums[left] > target)
					{
						left = mid + 1; 
					}
					else
					{
						right = mid;
					}
				}
			}
			else
			{
				if (nums[mid] < nums[right])
				{
					if (nums[right] < target)
					{
						right = mid;
					}
					else
					{
						left = mid + 1;
					}
				}
				else
				{
					if (nums[right] < target)
					{
						left = mid + 1;
					}
					else
					{
						right = mid; 
					}
				}				
			}			
		}

		mid = (left + right) / 2;
		if (nums[mid] == target)
		{
			pos = mid;			
		}
		return pos;
	}


	//int search(int A[], int n, int target) {
	//	int lo = 0, hi = n - 1;
	//	// find the index of the smallest value using binary search.
	//	// Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
	//	// Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
	//	while (lo<hi) {
	//		int mid = (lo + hi) / 2;
	//		if (A[mid]>A[hi]) lo = mid + 1;
	//		else hi = mid;
	//	}
	//	// lo==hi is the index of the smallest value and also the number of places rotated.
	//	int rot = lo;
	//	lo = 0; hi = n - 1;
	//	// The usual binary search and accounting for rotation.
	//	while (lo <= hi) {
	//		int mid = (lo + hi) / 2;
	//		int realmid = (mid + rot) % n;
	//		if (A[realmid] == target)return realmid;
	//		if (A[realmid]<target)lo = mid + 1;
	//		else hi = mid - 1;
	//	}
	//	return -1;
	//}
};

int _searchInRotatedSortedArray()
{
	vector<int> nums{ 4,5,6,7,8,1,2,3 }; // { 4, 5, 6, 7, 0, 1, 2 };
	int target = 8;

	Solution solu;
	int pos;

	pos = solu.search(nums, target);
	
	cout << "nums:" << endl;
	for (auto v : nums) cout << v << " ";
	cout << endl;
	cout << "target: " << target << endl;
	cout << "found: " << pos << endl;
	return 0;
}